The present invention relates to communication networks including local and broad area networks, and more particularly to an adaptive routing method in a communication network. This method is flexibly adapted to enable the status of a network in a multi-media integrated network for processing various information such as ISDN to change in a mixed manner, thus realizing effective usage and high-performance communication.
As shown in FIG. 1, a future network has an increased scale, speed, variety and capacity, developing a multi-media integrated network which can process a variety of mixed information. In such integrated networks, requirements such as communication speed, reliability and real-time features change greatly with respect to time and space. Therefore, there is a great demand for a network which is flexibly adaptive to these changes in network status and able to realize effective usage and high-performance communication.
Data, such as voice or image data, which require real-time operation may be subjected to a packetexchange method routine. In this case, to avoid damage to the real-time operation it is necessary to transmit data comprising a series of plural packets without separation. Effective usage and high network performance is required to satisfy this condition.
The number of nodes in present networks is 10.sup.2 to 10.sup.3 and the transmission speed is several hundred Kbps. In future networks, the number of nodes is predicted to be 10.sup.4 to 10.sup.5 and the transmission speed to be several hundred Mbps. It is necessary to develop network control technology which will be useful for a long time to come in the future.
Packet exchange network technology is used to realize the above communication. Exchange methods for packet exchange networks include the datagram method in which no logical link is set between terminals. Here, a setting-up concept is not used, instead a virtual call method (VC) setting up a logical channel between terminals. A fixed logical link set between terminals is called a permanent logical virtual circuit (PVC).
Before a setting-up is conducted in a packet network using a general virtual call method which does not use a permanent virtual circuit, the amount of traffic to be entered into a network is first predicted and the most appropriate route is chosen to prevent predicted traffic from being concentrated in a predetermined node between respective terminals. The bus information is maintained at respective nodes. A plurality of alternate routes is also provided between terminals to prepare for and avoid a node fault or a busy condition which exceeds the predicted traffic.
FIG. 2 shows a prior art method of setting routes between terminals and a packet exchange network. In FIG. 2, the exchange network comprises 6 nodes, 1-6, and four terminals, 7-10. For example, between terminals 8 and 10, the route from node 2 to node 4 via node 3 is the most appropriate. In addition, there are two alternate routes: from node 2 via nodes 3 and 6, and from node 2- via nodes 5 and 6. When a virtual call is set up in such a network, the node containing the transmitting terminal collects the status of the network, i.e., faults or busy conditions, and selects the most appropriate route, or an alternative route. A packet is then transmitted along the route, to perform a setting up.
In a multi-media integrated large-scale network through which a great amount of data such as burst data or image data is transmitted, the width of the change of the media to be included with respect to the time and quantity becomes too large to be handled by the prior art methods. Therefore, for a virtual call, it is difficult to obtain the most appropriate route between terminals to adequately distribute network traffic, by predicting the manner of media usage.
To prepare a plurality of alternative routes, time is required to collect information from the entire network. Thus, the obtained route does not reflect the traffic condition of the current network, and the high speed and large capacity demanded by respective media cannot be provided.
FIG. 3 shows an example of the structure of a communication network system using the datagram method. In FIG. 3, nodes 11, 12 and 13 are connected to each other through links 14, 15 and 16. Respective nodes are connected to other nodes to input ports and output ports not shown in FIG. 3. Node 11 is connected to terminals A, B, and C, node 12 is connected to terminal D, and node 13 is connected to terminals E and F. Information transmitted through this network system is divided into packet units as shown in FIG. 3, with header H storing destination information attached to the head of respective packet units.
In FIG. 3, we suppose that information "a" of terminal A is transmitted to terminal D, information "b" of terminal B is transmitted to terminal E, and information "c" of terminal C is transmitted to terminal F. Nodes 11, 12 and 13 have respective routing tables 17, 18 and 19, showing which link should be selected as the data transmission path with regard to the respective destination nodes. Information "a" comprises two packets ` and 2 , information "b" comprises three packets 1 - 3 and information "c" has four packets 1 - 4 .
Node 11 refers to routing table 17 which is based on the destination address attached to a packet input from terminals A, B and C through an input port and which selects an output port, thereby performing a routing. As a result, node 11 outputs packet data to link 14 and link 15 through respective output ports. For example, packet and "a 1 " and "a 2 " of terminal A and packet data "c" of terminal C are, for example, transmitted to link 15. In FIG. 3, only packet data c 4 is separated from other packet data ( 1 - 3 ) transmitted from the same terminal C and transmitted to link 15. This is because the traffic of link 14 is busy.
In a method which sets no logical links between terminals, namely, in a data gram method which does not use a setting-up concept, communication ends when the terminal transmits a packet into a network. The network detects the destination of the respective packet and transmits it to the terminal designated by the destination.
Only information "a" among packet data entering node 12 through link 15 is restructured as data and output to terminal D. On the other hand, the packet data "c 4 " are transmitted to link 16. Node 13 restructures packet data transmitted through links 14 and 16 and outputs information "b" at terminal B and information "c" at terminal F.
So-called adaptive routing transmits information in packet units to different links in accordance with a busy status of a link or a fault of a link or node, thereby achieving effective network usage and high-performance communication. In adaptive routing, a control system in respective nodes, as shown in FIG. 4, collects the varying statuses of all the nodes as whole information, calculates the most appropriate solution, corrects the route to reach the destination and periodically realizes the content of a routing paper, in accordance with a change in network status.
However, when the scale of a network becomes large and a great amount of data such as image data is transmitted through it in a bursty manner it takes a relatively long period to calculate the most appropriate path to reach the destination node based on the time required to collect the status information. The path which is actually used for transmitting packet data only reflects the status of a network which is fairly old and does not reflect the traffic condition of the current network. Therefore, it is difficult to achieve a real-time routing adaptive to the status of a network when the change in the load is great.
For data such as voice and image, which demands real-time operation, routing must be decided individually for each packet. Consequently, delay in processing increases, variation in arrival time of a packet at a destination node increases, and performance of the real-time operation demanded by the data cannot be satisfied.
When a fault occurs in a node or link, communication becomes impossible for a long period of time while the respective nodes collect fault information of other nodes or links and calculate the most appropriate path to the destination node. All the packets transmitted during this period are disposed of and in the worst case, it is necessary to re-start communication among end terminals.
As a general rule in such routing, the processsing time for routing should be as short as possible. Thus, optimum performance cannot be constantly provided to comply with quick variations in the network if the optimum network condition for performing a calculation of the optimum path remains fixed. The optimum network condition is determined by whether or not a uniformity of loads exists at respective nodes in a network, namely, whether the load distribution is considered important and whether or not or it is considered important to enable the packet to approach the destination node as close as is possible.